An information processing system having numerous information processing devices that are multi-dimensionally connected with one another is called a parallel computer system. One of the most ideal networks for connecting numerous information processing devices in the parallel computer system may be a full connection system in which each information processing device is connected to all the other information processing devices on a one-to-one basis. However, in such a full connection system, cost of cables utilized for connecting the information processing devices is increased, and a problem concerning the complexity of cable interconnection may be expected. Thus, it may be difficult to apply the full connection system to the network system having numerous information processing devices.
A widely used system alternative to the full connection system may be a system formed by utilizing a topology such as multidimensional torus or multidimensional mesh. Such a system utilizing the multidimensional torus topology or multidimensional mesh topology may be implemented by connecting only a few information processing devices to one information processing device on the one-to-one basis. As a result, all the information processing devices included in the network system are connected with one another. With such a network system, any of the information processing devices may eventually be accessible to all the other information processing devices included in the network system by connecting the information processing devices via other information processing devices. That is, any of the information processing devices may, in principle, be accessible to any other of the information processing devices in the network system.
However, in the network system utilizing the multidimensional torus or multidimensional mesh topology, not all the information processing devices are mutually connected on the one-to-one basis. Thus, the following problems may be of concern. That is, there is only one shortest path for transferring data from a certain information processing device to another information processing device in the full connection system; however, there are plural shortest paths for transferring data between the information processing devices in the network system utilizing the multidimensional torus or multidimensional mesh topology. Thus, a routing algorithm for selecting one of the shortest paths may be required.    [Patent Document 1] Japanese Laid-open Patent Publication No. 2004-527176    [Patent Document 2] Japanese Laid-open Patent Publication No. 08-185380    [Patent Document 3] Japanese Laid-open Patent Publication No. 07-191947    [Patent Document 4] Japanese Laid-open Patent Publication No. 06-266684    [Patent Document 5] Japanese Laid-open Patent Publication No. 10-021208    [Patent Document 6] U.S. Pat. No. 6,674,720    [Non-Patent Document 1] “Age-based packet arbitration in large radix k-ary and n-cubes”, Denis Abts and Deborah Weisser, SC07, 2007    [Non-Patent Document 2] “Routing and flow control in systems network algorithm”, V. Ahuja, IBM Journal, 1978    [Non-Patent Document 3] “Flexible oblivious router algorithm”, U. Par et. al., IBM Journal, 1995    [Non-Patent Document 4] “Computer Architecture A Quantitive Approach Fourth Edition”, John L. Hennessy and David A. Patterson, SHOEISHA Co., Ltd., Appendix E, E-3 p. 22—Overview, E-4 p. 30—Topology related section, E-5 p. 45—Routing related section, E-6 p. 57—switch micro-architecture related section